πŸ‘©β€πŸ’» 2225. ν•©λΆ„ν•΄

@Seongukbaek Posted December 22, 2021 Β· Updated December 22, 2021 Β· 2 min read

문제

0λΆ€ν„° NκΉŒμ§€μ˜ μ •μˆ˜ K개λ₯Ό λ”ν•΄μ„œ κ·Έ 합이 N이 λ˜λŠ” 경우의 수λ₯Ό κ΅¬ν•˜λŠ” ν”„λ‘œκ·Έλž¨μ„ μž‘μ„±ν•˜μ‹œμ˜€.

λ§μ…ˆμ˜ μˆœμ„œκ°€ 바뀐 κ²½μš°λŠ” λ‹€λ₯Έ 경우둜 μ„Όλ‹€(1+2와 2+1은 μ„œλ‘œ λ‹€λ₯Έ 경우). λ˜ν•œ ν•œ 개의 수λ₯Ό μ—¬λŸ¬ 번 μ“Έ μˆ˜λ„ μžˆλ‹€.

μž…λ ₯

  • 첫째 쀄에 두 μ •μˆ˜ N(1 ≀ N ≀ 200), K(1 ≀ K ≀ 200)κ°€ μ£Όμ–΄μ§„λ‹€.

좜λ ₯

  • 첫째 쀄에 닡을 1,000,000,000으둜 λ‚˜λˆˆ λ‚˜λ¨Έμ§€λ₯Ό 좜λ ₯ν•œλ‹€.

πŸ“ Logic

for (int i=0; i<201 ;i++) { dp[i][0] = 1; dp[1][i] = 1; } for (int i=0;i<=N;i++) dp[2][i] = i+1;
  • dp λ°°μ—΄ μ΄ˆκΈ°ν™”
  • i개의 μ •μˆ˜λ‘œ jλ₯Ό λ§Œλ“œλŠ” 경우의 μˆ˜κ°€ dp[i][j]에 μ €μž₯
for (int i=3;i<=K;i++) { for (int j=1;j<=N;j++) { for (int k=0;k<=j;k++) { dp[i][j] += dp[i-1][k]%1000000000; } } }
  • 점화식은 예λ₯Ό λ“€μ–΄, dp[3][1]을 κ΅¬ν•˜λŠ” 경우, 즉 3개의 μ •μˆ˜λ‘œ 1을 λ§Œλ“€μ–΄μ•Ό ν•˜λŠ” 경우의 μˆ˜λŠ” dp[2][0] + dp[2][1]둜, 2개의 μ •μˆ˜λ‘œ 0을 λ§Œλ“œλŠ” 경우의 μˆ˜μ™€ 2개의 μ •μˆ˜λ‘œ 1을 λ§Œλ“œλŠ” 경우의 수λ₯Ό λ”ν•˜λ©΄ λœλ‹€
  • λ”°λΌμ„œ, dp[i][j] = dp[i-1][0] + ... + dp[i-1][j]κ°€ λœλ‹€

πŸ“„ CODE

μ½”λ“œ 보기/μ ‘κΈ°πŸ’«
import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { static long dp[][] = new long[201][201]; public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String tc = br.readLine(); StringTokenizer st = new StringTokenizer(tc, " "); int N = Integer.parseInt(st.nextToken()); int K = Integer.parseInt(st.nextToken()); for (int i=0; i<201 ;i++) { dp[i][0] = 1; dp[1][i] = 1; } for (int i=0;i<=N;i++) dp[2][i] = i+1; for (int i=3;i<=K;i++) { for (int j=1;j<=N;j++) { for (int k=0;k<=j;k++) { dp[i][j] += dp[i-1][k]%1000000000; } } } System.out.println(dp[K][N]%1000000000); } }

✏️ Review

  • μ˜€λžœλ§Œμ— μ•Œκ³ λ¬Έμ œλ₯Ό ν‘ΈλŠ” 터라 아이디어λ₯Ό μž‘λŠ”λ° ν•œμ°Έ 걸렸던 것 κ°™λ‹€
  • 막상 점화식을 λ„μΆœν•΄λ‚΄λ©΄ μ‰¬μš΄ λ¬Έμ œμ˜€μ§€λ§Œ 점화식 λ„μΆœμ΄ μ–΄λ €μ› κ³ , 처음으둜 java둜 ν‘Ό λ¬Έμ œμ—¬μ„œ λΈ”λ‘œκ·Έλ₯Ό μ°Έκ³ ν–ˆλ‹€

πŸ“• 좜처

https://www.acmicpc.net/problem/2225

@Seongukbaek
배우고 μ •λ¦¬ν•˜κ³  κ³΅μœ ν•˜λŠ” λŒ€ν•™μƒ λ°±μ„±μš±μž…λ‹ˆλ‹€ πŸ˜€